上帝造题的七分钟

Time Limit: 20 Sec Memory Limit: 128 MB

Description

“第一分钟，X说，要有矩阵，于是便有了一个里面写满了0的n×m矩阵。
　　第二分钟，L说，要能修改，于是便有了将左上角为(a,b)，右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作。
　　第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。
　　第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。
　　第五分钟，和雪说，要有耐心，于是便有了时间限制。
　　第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。
　　第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”
　　 ——《上帝造裸题的七分钟》
　　所以这个神圣的任务就交给你了。

Input

输入数据的第一行为X n m，代表矩阵大小为n×m。
　　从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：
　　　　L a b c d delta —— 代表将(a,b),(c,d)为顶点的矩形区域内的所有数字加上delta。
　　　　k a b c d　　 —— 代表求(a,b),(c,d)为顶点的矩形区域内所有数字的和。
　　请注意，k为小写。

Output

对于每个操作，输出一个答案。

Sample Input

X 4 4
　L 1 1 3 3 2
　L 2 2 4 4 1
　k 2 2 3 3

Sample Output

12

HINT

1<=n,m<=2048, |delta|<=500, 操作数<=200000.

Main idea

维护一个数据结构，支持矩阵加减一个数，矩阵求和。

Solution

我们运用二维树状数组。

直接维护显然不行，我们令 A[i][j] 表示 (i,j) 到 (n,m) 的矩阵加的东西，然后推一下式子：

img

那么再维护一个 A[i][j]*i, A[i][j]*j, A[i][j]ij，即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 2050;

int n,m;
int x_1,y_1,x_2,y_2,z;
char c[3];

int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

struct Bit
{
    int C[ONE][ONE];
    int lowbit(int x) {return x&-x;}

    void Add(int x,int y,int z)
    {
        for(int i=x;i<=n;i+=lowbit(i))
            for(int j=y;j<=m;j+=lowbit(j))
                C[i][j] += z;
    }

    int Query(int x,int y)
    {
        int res = 0;
        for(int i=x;i>=1;i-=lowbit(i))
            for(int j=y;j>=1;j-=lowbit(j))
                res += C[i][j];
        return res;
    }

}A,Ai,Aj,Aij;

void Add(int x,int y,int z)
{
    A.Add(x,y,z);    Ai.Add(x,y,z*x);    Aj.Add(x,y,z*y);    Aij.Add(x,y,z*x*y);
}

int Get(int x,int y)
{
    return A.Query(x,y)*(x*y+x+y+1) - Ai.Query(x,y)*(y+1) - Aj.Query(x,y)*(x+1) + Aij.Query(x,y);
}

int main()
{
    scanf("X %d %d",&n,&m);
    while(scanf("%s",&c)!=EOF)
    {
        scanf("%d%d%d%d", &x_1, &y_1, &x_2, &y_2);
        if(c[0]=='L')
        {
            scanf("%d", &z);
            Add(x_1,y_1,z);    Add(x_2+1,y_1,-z);    Add(x_1,y_2+1,-z);    Add(x_2+1,y_2+1,z);
        }
        else
        {
            printf("%d\n",Get(x_2,y_2) - Get(x_1-1,y_2) - Get(x_2,y_1-1) + Get(x_1-1,y_1-1));
        }
    }
}